﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Diagnostics;
using LingDong.IndexReader;
using LingDong.IndexEntities.Dictionary;
using PanGu;

namespace LingDong.WordCluster
{
    public class Cluster
    {
        public Cluster(string term, Index index)
        {
            this.term = term;
            this.index = index;
        }

        public void Run()
        {
            // get all related word list
            termAppearNum = 0;
            Dictionary<string, int> relatedWord = new Dictionary<string, int>();
            termDocList = new Dictionary<string, List<int>>();
            Dictionary<int, InvertedListEntity> invertedList = index.GetInvertedList(term);
            foreach (InvertedListEntity inv in invertedList.Values)
            {
                termAppearNum += inv.HitList.Count;
                AddOneDocument(inv, relatedWord);
            }
            relatedWord.Remove(term);

            // sort and get first 200 related words
            Dictionary<string, double> mutualInfo = CalculateMutualInfo(relatedWord);
            List<string> terms =
                (from t in mutualInfo
                 orderby t.Value descending
                 select t.Key).
                 Take(Settings.ClusterWordCountForEachClustering).
                 ToList();

            // cluster and save
            List<List<string>> clusterTerms = ClusterTerms(terms);
            SaveToFile(term, clusterTerms);
        }

        #region Related Word List

        private void AddOneDocument(InvertedListEntity inv, Dictionary<string, int> relatedWord)
        {
            Dictionary<string, int> curDocTermList = new Dictionary<string, int>();
            foreach (HitListEntity hit in inv.HitList)
            {
                string sen = index.GetParsedDocument(inv.DocID).SentenceList[hit.SentenceIndex];
                string[] wordList = new Segment().DoSegment(sen).Select(info => info.Word).Distinct().ToArray();
                foreach (string word in wordList)
                {
                    if (IndexCache.ContainsNoun(word))
                    {
                        CommonUtility.Utility.AddItemCount<string>(relatedWord, word);
                        CommonUtility.Utility.AddItemCount<string>(curDocTermList, word);
                    }
                }
            }
            foreach (string term in curDocTermList.Keys)
            {
                CommonUtility.Utility.AddItemCount<string>(termDocList, term, inv.DocID);
            }
        }

        private Dictionary<string, double> CalculateMutualInfo(Dictionary<string, int> relatedWord)
        {
            Dictionary<string, double> result = new Dictionary<string, double>();
            foreach (KeyValuePair<string, int> word in relatedWord)
            {
                result[word.Key] = CalculateOneMutual(word.Key, word.Value);
            }
            return result;
        }

        private double CalculateOneMutual(string word, int bothAppearNum)
        {
            if (bothAppearNum <= 1)
                return 0;

            double N = IndexCache.TotalSentenceCount;
            double[,] n = new double[2, 2];
            n[1, 1] = bothAppearNum;
            n[1, 0] = termAppearNum - bothAppearNum;
            n[0, 1] = IndexCache.GetTermOccurrenceNumber(word) - bothAppearNum;
            n[0, 0] = N - n[1, 1] - n[1, 0] - n[0, 1];

            double rank = 0.0;
            for (int i = 0; i < 2; i++)
            {
                for (int j = 0; j < 2; j++)
                {
                    double ni_ = n[i, 0] + n[i, 1];
                    double n_j = n[0, j] + n[1, j];
                    rank += n[i, j] / N *
                        Math.Log(N * n[i, j] / ni_ / n_j, 2);
                }
            }
            return rank;
        }

        #endregion
        
        
        #region Cluster Term

        private List<List<string>> ClusterTerms(List<string> terms)
        {
            int count = terms.Count;
            bool[,] g = new bool[count, count];

            FillTermDirectRelation(g, terms);
            FloydAlgorithm(g);
            return GetClusterTermList(g, terms);
        }

        private int GetListCommonNum(List<int> a, List<int> b)
        {
            int i, j, counta, countb, count;
            counta = a.Count;
            countb = b.Count;
            i = j = count = 0;
            while (i < counta && j < countb)
            {
                if (a[i] < b[j])
                    i++;
                else
                    if (a[i] > b[j])
                        j++;
                    else
                    {
                        count++;
                        i++; j++;
                    }
            }
            return count;
        }

        private void FillTermDirectRelation(bool[,] g, List<string> terms)
        {
            int count = g.GetLength(0);
            for (int i = 0; i < count; i++)
            {
                for (int j = i + 1; j < count; j++)
                {
                    List<int> listA = termDocList[terms[i]];
                    List<int> listB = termDocList[terms[j]];
                    int commonNum = GetListCommonNum(listA, listB);
                    if (commonNum >= listA.Count * Settings.SimilaryThreshold)
                        g[i, j] = true;
                    if (commonNum >= listB.Count * Settings.SimilaryThreshold)
                        g[j, i] = true;
                }
            }
        }

        private void FloydAlgorithm(bool[,] g)
        {
            int count = g.GetLength(0);
            Debug.Assert(count <= 200);
            for (int i = 0; i < count; i++)
                g[i, i] = true;
            for (int k = 0; k < count; k++)
                for (int i = 0; i < count; i++)
                    for (int j = 0; j < count; j++)
                        g[i, j] = g[i, j] || g[i, k] && g[k, j];
        }

        private List<List<string>> GetClusterTermList(bool[,] g, List<string> terms)
        {
            int count = g.GetLength(0);
            bool[] flag = new bool[count];
            for (int j = 0; j < count; j++)
                flag[j] = true;

            List<List<string>> list = new List<List<string>>();
            while (true)
            {
                int max_ct = -1;
                int k = -1;
                for (int i = 0; i < count; i++)
                {
                    if (flag[i] == false)
                        continue;
                    int ct = 0;
                    for (int j = 0; j < count; j++)
                    {
                        if (flag[j] == false)
                            continue;
                        if (g[j, i] && g[i, j]) ct++;
                    }
                    if (ct > max_ct)
                    {
                        k = i;
                        max_ct = ct;
                    }
                }

                if (k == -1)
                    break;

                List<string> new_list = new List<string>();
                for (int i = 0; i < count; i++)
                {
                    if (flag[i] == false)
                        continue;
                    if (g[i, k] && g[k, i])
                    {
                        if (new_list.Count < Settings.ClusterWordCountForEachClass)
                            new_list.Add(terms[i]);
                        flag[i] = false;
                    }
                }
                list.Add(new_list);

                if (list.Count == Settings.MaxClusterCount)
                    return list;
            }
            return list;
        }

        #endregion


        private void SaveToFile(string term, List<List<string>> clusterTerms)
        {
            using (StreamWriter sw = new StreamWriter(Settings.OutputFile, true))
            {
                foreach (List<string> list in clusterTerms)
                {
                    if (list.Count <= 0)
                        continue;

                    sw.WriteLine("@URL: http://@{0}/{1}", term, list[0]);
                    list.ForEach(t => { sw.Write(t); sw.Write("\t"); });
                    sw.WriteLine();
                }
                sw.WriteLine();
            }
        }

        private string term;
        private Index index;
        private int termAppearNum;
        private Dictionary<string, List<int>> termDocList;
    }
}
